#include <iostream>
#include <vector>
#include <numeric>
using namespace std;

// 通过比较两部分的重量可知哪一部分中含有假币
int sum(vector<int> vec, int low, int high)
{
	return accumulate(vec.begin() + low, vec.begin() + high + 1, 0);
}

// 二分查找
int forgery(vector<int> coins, int low, int high)
{
	if (low == high)
		return low;
	else if (low == high - 1)
	{
		return coins[low] < coins[high] ? low : high;
	}

	int mid = (low + high) >> 1;
	if ((low + high) & 1)	// 偶数(指数组大小)分两堆
		return sum(coins, low, mid) < sum(coins, mid + 1, high) ? forgery(coins, low, mid) : forgery(coins, mid + 1, high);
	else
	{
		// 奇数分为左、右、mid三堆
		if (sum(coins, low, mid - 1) < sum(coins, mid + 1, high))
			return forgery(coins, low, mid - 1);
		else if (sum(coins, low, mid - 1) > sum(coins, mid + 1, high))
			return forgery(coins, mid + 1, high);
		else
			return mid;
	}
}

int main()
{
	vector<int> coins{ 100, 98,100,100 };

	cout << "Number " << forgery(coins, 0, coins.size()-1) + 1 << " is fake!" << endl;	// 2 is fake
	return 0;
}